package day03;

/**
 * @author aiPlusPlus
 * @version 1.0
 * @date 2022/12/3 15:09
 */

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 给定一棵二叉树的根节点 root 和树中的一个节点 u ，返回与 u 所在层中距离最近的右侧节点，当 u 是所在层中最右侧的节点，返回 null 。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：root = [1,2,3,null,4,5,6], u = 4
 * 输出：5
 * 解释：节点 4 所在层中，最近的右侧节点是节点 5。
 * 示例 2：
 *
 *
 *
 * 输入：root = [3,null,4,2], u = 2
 * 输出：null
 * 解释：2 的右侧没有节点。
 * 示例 3：
 *
 * 输入：root = [1], u = 1
 * 输出：null
 * 示例 4：
 *
 * 输入：root = [3,4,2,null,null,null,1], u = 4
 * 输出：2
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution2 {
    public TreeNode findNearestRightNode(TreeNode root, TreeNode u) {
        Queue<TreeNode> bfs = new LinkedList<>();
        bfs.add(root);
        List<List<TreeNode>> list = new ArrayList<>();
        while (!bfs.isEmpty()){
            List<TreeNode> list1 = new ArrayList<>();
            int size = bfs.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = bfs.poll();
                if (poll!=null) {
                    list1.add(poll);
                    bfs.add(poll.left);
                    bfs.add(poll.right);
                }
            }
            if(list1.size()!=0){
                list.add(list1);
            }
        }
        for (List<TreeNode> treeNodes : list) {
            for (int i = 0; i < treeNodes.size(); i++) {
                if(treeNodes.get(i)==u){
                    if(i==treeNodes.size()-1){
                        return null;
                    }else {
                        return treeNodes.get(i+1);
                    }
                }
            }
        }
        return null;
    }
}
